package linkcut;


public class LinkCutTree<V extends Comparable<V>> {
	public AuxVertex<V> makeTree(V value) {
		return new AuxVertex<V>(value);
	}
	
	public AuxVertex<V> makeTree() {
		return new AuxVertex<V>(null);
	}
	
	/**
	 * Adds v to w as a child. The vertexes should be nodes of distinct trees.
	 * @param v should be a root
	 * @param w new parent for v
	 * @throws IllegalArgumentException if v is not a root
	 */
	public void link(AuxVertex<V> v, AuxVertex<V> w) {
		if (!v.isRoot()) {
			throw new IllegalArgumentException("The first vertex should be a root");
		}
		access(v);
		access(w);
		if (v.getLeft() != null) {
			v.getLeft().detachFromParent();
		}
		v.attachLeft(w);
	}
	
	public void cut(AuxVertex<V> v) {
		access(v);
		AuxVertex<V> temp = v.getLeft();
		if (temp != null) {
			temp.detachFromParent();
		}
	}
	
	public AuxVertex<V> findRoot(AuxVertex<V> v) {
		access(v);
		while (v.getLeft() != null) {
			v = v.getLeft();
		}
		access(v);
		return v;		
	}
		
	private void access(AuxVertex<V> v) {
		SplayTools.splay(v);
		AuxVertex<V> temp = v.getRight();
		
		if (temp != null) {
			temp.detachFromParent();
			temp.setPathParent(v);
		}
		
		temp = v;

		while (temp.getPathParent() != null) {
			AuxVertex<V> w = temp.getPathParent();
			SplayTools.splay(w);
			if (w.getRight() != null) {
				w.getRight().setPathParent(w);
			}
			if (w.getRight() != null) {
				w.getRight().detachFromParent();
			}
			if (temp.getParent() != null) {
				temp.detachFromParent();
			}
			w.attachRight(temp);
			temp.setPathParent(null);
			temp = w;
		}
		SplayTools.splay(v);
		
		if (v.getRight() != null) {
			throw new IllegalStateException("Right child after access");
		}
	}
	
	public boolean isRepresentedRoot(AuxVertex<V> v) {
		if (v.getLeft() != null) {
			return false;
		}
		while(v.getParent() != null) {
			v = v.getParent();
		}
		return v.getPathParent() == null;
	}
}
